package com.tingyuge.base.arithmetic.sort;

/**
 * Created by xiaodao
 * date: 2020/4/6
 * 归并排序
 */
public class MergeSort<T extends Comparable <T>> extends Sort<T>  {
    private T[] leftArray;
    @Override
    protected void sort() {
        leftArray = (T[]) new Comparable[array.length >>1];

        sort(0,array.length);
    }

    /**
     *  对 [begin ,end ]进行范围排序
     * @param begin
     * @param end
     */
    private void sort(int begin,int end){
        if((end -  begin) <2) return;
        int mid =(begin+ end) >>1;
        sort(begin,mid);
        sort(mid,end);
        merge(begin,mid,end);
    }

    /**
     * 将 [begin,mid)[mid,end] 合并
     * @param begin
     * @param mid
     * @param end
     */
    private void merge(int begin, int mid, int end) {
        //左边的开始=0 左边的结束 end-begin
        int li=0,le =mid -begin;
        //右边的开始就是mid  结束就是end
        int ri=mid, re =end;
        //新的数组的索引
        int ai = begin  ;

        //备份左边的数组
        for (int i = li; i < le; i++) {
            //
            leftArray[i]=array[begin+i];

        }
        //如果左边还没有结束
        while (li <le){
            //这里右边比左边小的话.
//            Integers.println((Integer[]) array);
//            System.out.println(array[3]);
//            if(array[ri]==null || leftArray[li]== null){
//                System.out.println("ri:"+ri+" li:"+li+" array[ri]:" +array[ri] +"  leftArray[li]:" +leftArray[li]);
//            }

            if(ri< re && cmpElement(array[ri],leftArray[li]) < 0){
                array[ai++] = array[ri++];

            }else {
                array[ai++] = leftArray[li++];
            }


        }

    }
}
